package com.algorithm.learning.base.二叉树;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/24 23:15
 **/
public class 是否有路径和 {

    /**
     * 给你一棵树，和一个值，判断这棵树的是否存在某条路径上的节点值之和等于这个值。
     * 例如：
     *           1
     *        ↙     ↘
     *       2       4
     *        ↘     ↙ ↘
     *         3   5   7
     * 上面是一颗二叉树，再给你一个值12
     * 那么满足条件的路径只有1->4->7, 因为 1 + 4 + 7 =12
     * @param root
     * @param sum
     * @return
     */
    private static boolean isSum = false;
    public static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        doSum(root, 0, sum);
        return isSum;
    }

    private static void doSum(TreeNode root, int curSum, int sum) {
        // 这里如果, 节点没有左子树，也没有右子树，就表示该节点是叶子节点，那么当前路径和加上叶子节点的值，如果等于目标值，那么就表示存在路径和等于目标值的路径
        if (root.left == null && root.right == null) {
            curSum = curSum + root.value;
            isSum = curSum == sum;
        }
        // 否则，判断左右子树，如果存在，就继续递归
        curSum += root.value;
        if (root.left != null) {
            doSum(root.left, curSum, sum);
        }
        if (root.right != null) {
            doSum(root.right, curSum, sum);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        System.out.println(hasPathSum(root, 12));

    }
}
